


'''
Created on Jul 4, 2011

@author: vakumar
'''
from com.utils.util import Utils
#from com.sorts.sorter import Sorter



class MergeSorter(object):
    '''
    classdocs
    '''  
    def __init__(self, arr):
        '''
        Constructor
        '''
        self.arr = arr


    def __merge(self,left, right):
        i = j = 0
        res = []
        iMAX = len(left)
        jMAX = len(right)
        while True:
            if self.comparator(left[i],right[j]):
                res.append(left[i])
                i += 1
            else:
                res.append(right[j])
                j += 1
            if i == iMAX : return res + right[j:]
            if j == jMAX : return res + left[i:]    
            
        
    def __divide(self, arr):
        size = len(arr)
        if self.comparator(size,2, False):
            return arr
        mid = size/2
        return self.__merge(self.__divide(arr[:mid]), self.__divide(arr[mid:]))
    
    def dosort(self):
        print '*'*20
        print 'Merge Sort'
        print '*'*20
        print 'before sort : %s' %str(self.arr)
        self.comparator = Utils.comparator()
        result = self.__divide(self.arr)
        print 'after sort : %s' %str(result)
        print 'Comparision Performed:: %s' %Utils.count     
        self.count = Utils.count
        
    def getComparisonCount(self):
        return self.count
        
    def sort(self):
        self.comparator = Utils.comparator()
        self.__divide(self.arr)  
        self.count = Utils.count   
    